package com.jzoffer2;

import ds.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No34
 * @description
 * @date 2021/2/4 下午2:18
 */
public class No34 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode t1 = new TreeNode(4);
        TreeNode t2 = new TreeNode(8);
        TreeNode t3 = new TreeNode(11);
        TreeNode t4 = new TreeNode(3);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(7);
        TreeNode t7 = new TreeNode(2);
        TreeNode t8 = new TreeNode(5);
        TreeNode t9 = new TreeNode(1);

        root.left = t1;
        root.right = t2;
        t1.left = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
        t3.right = t7;
        t5.left = t8;
        t5.right = t9;

        List<List<Integer>> paths = pathSum(root,22);
        print(paths);
    }

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new ArrayList<>();
        if(root == null){
            return paths;
        }
        List<Integer> path = new ArrayList<>();
        getPathSum(root,sum,paths,path);
        return paths;
    }

    private static void getPathSum(TreeNode root, int sum, List<List<Integer>> paths, List<Integer> path) {
        if(root == null){
            return;
        }
        path.add(root.val);
        sum -= root.val;
        if(sum == 0 && isLeaf(root)){
            paths.add(new ArrayList<>(path));
        }
        getPathSum(root.left,sum,paths,path);
        getPathSum(root.right,sum,paths,path);
        path.remove(path.size() - 1);
    }

    private static boolean isLeaf(TreeNode root) {
        return root.left == null && root.right == null;
    }

    private static void print(List<List<Integer>> paths){
        int size = paths.size();
        for (int i = 0; i < size; i++) {
            List<Integer> path = paths.get(i);
            int subSize = path.size();
            for (int j = 0; j < subSize; j++) {
                System.out.print(path.get(j));
                System.out.print(" ");
            }
            System.out.println();
        }
    }


}
